package leetcode.calc._06_07;

import org.springframework.util.Assert;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：["()"]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 8
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _07_03_022_括号生成_DFS {
    public static void main(String[] args) {
        Solution sol = new _07_03_022_括号生成_DFS().new Solution();

        String str = "()((()))()";
        int index = 0;
        while ((index = str.indexOf("()", index)) != -1) {
            System.out.println(index);
            System.out.println(str.substring(0, index) + "(())" + str.substring(index + 2));
            index++;
        }

        if (true) {
            int param = 3;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[((())), (()()), (())(), ()(()), ()()()]";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int param = 1;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[()]";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int param = 4;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(), (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()]";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int param = 6;
            List<String> res = sol.generateParenthesis(param);
            String rel = "[(((((()))))), ((((()())))), ((((())()))), ((((()))())), ((((())))()), ((((()))))(), (((()(())))), (((()()()))), (((()())())), (((()()))()), (((()())))(), (((())(()))), (((())()())), (((())())()), (((())()))(), (((()))(())), (((()))()()), (((()))())(), (((())))(()), (((())))()(), ((()((())))), ((()(()()))), ((()(())())), ((()(()))()), ((()(())))(), ((()()(()))), ((()()()())), ((()()())()), ((()()()))(), ((()())(())), ((()())()()), ((()())())(), ((()()))(()), ((()()))()(), ((())((()))), ((())(()())), ((())(())()), ((())(()))(), ((())()(())), ((())()()()), ((())()())(), ((())())(()), ((())())()(), ((()))((())), ((()))(()()), ((()))(())(), ((()))()(()), ((()))()()(), (()(((())))), (()((()()))), (()((())())), (()((()))()), (()((())))(), (()(()(()))), (()(()()())), (()(()())()), (()(()()))(), (()(())(())), (()(())()()), (()(())())(), (()(()))(()), (()(()))()(), (()()((()))), (()()(()())), (()()(())()), (()()(()))(), (()()()(...";
            Assert.isTrue(rel.equals(res.toString()), String.format("\n%s !=\n%s", res , rel));
        }
    }
    class Solution {
        public List<String> generateParenthesis(int num) {
            // 递归组合
            ArrayList<String> list = new ArrayList<>();
            dfs(list, "(", num - 1, num);
            return list;
        }

        private void dfs(List<String> list, String str, int left, int right) {
            if (left == 0) {
                if (right == 0) {
                    list.add(str);
                    return;
                }
                dfs(list, str + ")", left, right - 1);
                return;
            } else if (left < right) {
                dfs(list, str + ")", left, right - 1);
            }
            dfs(list, str + "(", left - 1, right);
        }

    }
    
}
